import java.util.Map;

public class Test6 {
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    //不用考虑上面和左边是不是石头
    public int uniquePathsWithObstacles(int[][] obstacleGrid1) {
        int m = obstacleGrid1.length;
        int n = obstacleGrid1[0].length;
        int[][] obstacleGrid =new int[m + 1][n + 1];
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                obstacleGrid[i + 1][j + 1] = obstacleGrid1[i][j];
            }
        }
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.print(obstacleGrid[i][j]+" ");
            }
            System.out.println();
        }
        dp[0][1] = 1;
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(obstacleGrid[i - 1][j - 1] == 1) continue;
                if(obstacleGrid[i - 1][j] != 1) {
                    dp[i][j] += dp[i -1][j];
                }
                if(obstacleGrid[i][j - 1] != 1) {
                    dp[i][j] += dp[i][j - 1];

                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        Test6 test6 = new Test6();
        int[][] arr = {{0,0,0},{0,1,0},{0,0,0}};
        test6.uniquePathsWithObstacles(arr);

    }
}
